package 剑指offer;

import java.util.ArrayList;
import java.util.List;

public class 剑指Offer34二叉树中和为某一值的路径 {

    ArrayList<List<Integer>> lists = null;
    List<Integer> list = null;

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        this.lists = new ArrayList();
        this.list = new ArrayList();
        help(root,target,list,lists);
        return lists;
    }
    public void help(TreeNode root,int target,List<Integer> list,ArrayList<List<Integer>> lists){
        if(root == null) return;
        list.add(root.val);
        if(root.left == null && root.right == null && target - root.val == 0){
            List<Integer> l = new ArrayList<>();
            for (Integer integer : list) {
                l.add(integer);
            }
            lists.add(l);
            list.remove(list.size()-1);
            return;
        }
        //如果当前节点得值小于target，继续向叶子节点触发，否则不满足条件，返回空链表
        help(root.left,target-root.val,list,lists);
        help(root.right,target-root.val,list,lists);
        list.remove(list.size()-1);
    }




    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode node1 = new TreeNode(4);
        TreeNode node2 = new TreeNode(11);
        TreeNode node3 = new TreeNode(7);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(8);
        TreeNode node6 = new TreeNode(13);
        TreeNode node7 = new TreeNode(4);
        TreeNode node8 = new TreeNode(5);
        TreeNode node9 = new TreeNode(1);
        root.left = node1;
        root.right = node5;
        node1.left = node2;
        node2.left = node3;
        node2.right = node4;
        node5.left = node6;
        node5.right = node7;
        node7.left = node8;
        node7.right = node9;
        剑指Offer34二叉树中和为某一值的路径 o = new 剑指Offer34二叉树中和为某一值的路径();
        System.out.println(o.pathSum(root, 22));
    }
}
